#include <iostream>
using namespace std;

#include <string>
#include <vector>

class Solution {
public:
    const int N = 100010;
    long long countSubstrings(string s, char c)
    {
        vector<int> nums(N, -1);
        int j = 0, cnt = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (c == s[i])
            {
                nums[j++] = i;
                ++cnt;
            }
        }

        int tmp = cnt;
        for (int i = 0; i < j; i++)
        {
            if (nums[i] != -1)
            {
                cnt += --tmp;
            }
        }

        return cnt;
    }
};

int main()
{
    Solution s;
    string s1("abada");
    cout << s.countSubstrings(s1, 'a') << endl;

    return 0;
}